using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using Hashes;
using Hashes.StringHashes;

namespace ECollections
{
    /// <summary>
    /// A fast, memory efficient StringValueBag.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class StringValueBag<T> where T : IEquatable<T>
    {
        #region Constructors
        public StringValueBag()
        {
            Constructor(0, null, null);
        }
        /// <summary>
        /// Capacity specifies the initial size of the StringValueBag. The StringValueBag grows too accomodate more entries as they are added.
        /// </summary>
        /// <param name="capacity"></param>
        public StringValueBag(int capacity)
        {
            Constructor(capacity, null, null);
        }
        /// <summary>
        /// Capacity specifies the initial size of the StringValueBag. The StringValueBag grows too accomodate more entries as they are added.
        /// HashProviderA and HashProviderB are distinct hash providers for strings.
        /// </summary>
        /// <param name="capacity"></param>
        /// <param name="hashProviderA"></param>
        /// <param name="hashProviderB"></param>
        public StringValueBag(int capacity, ITwinHashCodeProvider<string> hashProvider)
        {
            Constructor(capacity, hashProvider, null);
        }
        public StringValueBag(int capacity, ITwinHashCodeProvider<string> hashProvider, IDictionary<string, T> dictionary)
        {
            Constructor(capacity, hashProvider, dictionary);
        }

        private void Constructor(int capacity, ITwinHashCodeProvider<string> hashProvider, IDictionary<string, T> dictionary)
        {
            // Minimum capacity of StringValueBag = 1024 entries
            _entries = new StringValueBagEntry<T>[(capacity > _minCapacity ? GetNextCapacity(capacity) : 1024)];
            // Initialize the space map
            _spaceMap = new BitArray((capacity > _minCapacity ? GetNextCapacity(capacity) : 1024));
            // Initialize the value space map
            _valueSpaceMap = new BitArray(GetNextPrime(_entries.Length * _numHashesValue));
            // If no hash provider is given, use default hash provider
            if (hashProvider == null)
                _hashProvider = (ITwinHashCodeProvider<string>)new DefaultTwinHashProvider();
            
            // If a dictionary is provided, add its members to present StringValueBag
            if (dictionary != null)
                AddCollection(dictionary);
        }
        #endregion

        #region Private Members
        // Used for thread synchronization
        private object _syncRoot = new object();
        // Number of items present in StringValueBag
        private int _count;
        // Hash Providers
        private ITwinHashCodeProvider<string> _hashProvider;
        // StringValueBag entries
        private StringValueBagEntry<T>[] _entries;
        // The number of hashes to use by default. A higher number will provide higher load factor. A lower number will provide greater performance.
        private int _numHashes = 31;
        // Mininum Capacity of StringValueBag
        private readonly int _minCapacity = 1024;
        // The space map for the dictionary
        private BitArray _spaceMap;
        // The space map for the values
        private BitArray _valueSpaceMap;
        private readonly int _numHashesValue = 8;
        private IHashProvider<T> _valueHashProvider;
        #endregion

        #region Public Methods
        /// <summary>
        /// This methods adds a given Key value pair to the StringValueBag. Keys need to be unique. Values need not be unique.
        /// Complexity Average Case: O(log((n + 1/)n)), Worst Case: O(n)
        /// </summary>
        /// <param name="key"></param>
        /// <param name="keyValue"></param>
        public void Add(string key, T keyValue)
        {
            if (string.IsNullOrEmpty(key))
                throw new ArgumentNullException("key");
            AddInternal(key, keyValue);
        }
        /// <summary>
        /// Removes a given Key-Value pair from the dictionary. If the specified key does not exist in the StringValueBag, False is returned.
        /// Complexity O(1)
        /// </summary>
        /// <param name="key"></param>
        public bool Remove(string key)
        {
            if (string.IsNullOrEmpty(key))
                throw new ArgumentNullException("key");

            int index = ContainsKeyInternal(key);
            // If key is present in dictionary, a value >= 0 is returned
            if (index >= 0)
            {
                lock (_syncRoot)
                {
                    _spaceMap.Set(index, false);
                    _count--;
                }
                return true;
            }
            else
                return false;
            // throw new Exception("Key does not exist in dictionary");   
        }

        /// <summary>
        /// Determines whether a given key exists in the StringValueBag. 
        /// Complexity O(1)
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public bool ContainsKey(string key)
        {
            if (string.IsNullOrEmpty(key))
                throw new ArgumentNullException("key");

            if (ContainsKeyInternal(key) >= 0)
                return true;
            else
                return false;
        }
        /// <summary>
        /// Determines whether a given Value exists in the StringValueBag
        /// Complexity O(n)
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        public bool ContainsValue(T val)
        {
            for (int i = 0; i < _entries.Length; i++)
            {
                if (_spaceMap[i] && _entries[i].Value.Equals(val))
                    return true;
            }
            return false;
        }

        public bool ProbablyContainsValue(T val)
        {
            for (int i = 0; i < _numHashesValue; i++)
            {
                if (ValueHashProvider == null)
                {
                    if (! _valueSpaceMap.Get((int)(val.GetHashCode() * _primes[i]) & (Capacity - 1)))
                        return false;
                }
                else
                    if (!_valueSpaceMap.Get((int)(ValueHashProvider.GetHashCode(val) * _primes[i]) & (Capacity - 1)))
                        return false;
            }
            return true;
        }

        /// <summary>
        /// Clears all the Key-Value pairs from the StringValueBag.
        /// Complexity O(1)
        /// </summary>
        public void Clear()
        {
            _entries = new StringValueBagEntry<T>[_minCapacity];
            _spaceMap.SetAll(false);
            _valueSpaceMap.SetAll(false);
        }
        /// <summary>
        /// Gets the number of items present in the StringValueBag
        /// </summary>
        public int Count
        {
            get { return _count; }
        }
        /// <summary>
        /// Gets the maximum number of items the StringValueBag can contain without resizing
        /// </summary>
        public int Capacity
        {
            get { return _entries.Length; }
        }
        /// <summary>
        /// Gets the first HashProvider being used by the StringValueBag
        /// </summary>
        public ITwinHashCodeProvider<string> HashProvider
        {
            get { return _hashProvider; }
        }       
        /// <summary>
        /// The number of hashes to generate for insertions / lookups in the StringValueBag.
        /// The default value is 31. Possible values range from 5 to 277 inclusive. A lower value leads to greater performance at the cost of a low load factor.
        /// A higher value leads to lesser performance but higher load factor.
        /// </summary>
        public int NumHashes
        {
            get { return _numHashes; }
            set { _numHashes = ((value < 16) && (value > 278) ? value : 31); }
        }
        /// <summary>
        /// The HashProvider for TValue type
        /// </summary>
        public IHashProvider<T> ValueHashProvider
        {
            get
            {
                return _valueHashProvider;
            }
            set
            {
                _valueHashProvider = value;
            }
        }
        // Indexer
        public T this[string key]
        {
            get
            {
                if (string.IsNullOrEmpty(key))
                    throw new ArgumentNullException("key");

                int index;
                if ((index = ContainsKeyInternal(key)) >= 0)
                    return _entries[index].Value;
                else
                    return default(T);
            }
            set
            {
                int index;
                if ((index = ContainsKeyInternal(key)) >= 0)
                    _entries[index].Value = value;
                else
                    throw new KeyNotFoundException("Key not found. Key: " + key);
            }
        }
        #endregion

        #region Utility Functions
        /// <summary>
        /// The internal method used by Add(string, T) method.
        /// </summary>
        /// <param name="key"></param>
        /// <param name="val"></param>
        private void AddInternal(string key, T val)
        {
            uint hashA, hashB;
            uint hash;
            bool inserted = false;
            HashProvider.GetHashCodes(key, out hashA, out hashB);
            lock (_syncRoot)
            {
                for (int i = 0; i < NumHashes; i++)
                {
                    hash = hashA + _primes[i] * hashB;
                    if (!_spaceMap[(int)(hash & (this.Capacity - 1))])
                    {
                        _entries[hash & (this.Capacity - 1)] = new StringValueBagEntry<T>(hashA, hashB, val);
                        inserted = true;
                        _spaceMap[(int)(hash & (this.Capacity - 1))] = true;
                        UpdateValueSpaceMapInsert(val);
                        _count++;
                        break;
                    }
                }
                if (!inserted)
                {
                    while (!inserted)
                    {
                        Resize();
                        for (int i = 0; i < NumHashes; i++)
                        {
                            hash = hashA + _primes[i] * hashB;
                            if (!_spaceMap[(int)(hash & (this.Capacity - 1))])
                            {
                                _entries[hash & (this.Capacity - 1)] = new StringValueBagEntry<T>(hashA, hashB, val);
                                inserted = true;
                                _spaceMap[(int)(hash & (this.Capacity - 1))] = true;
                                UpdateValueSpaceMapInsert(val);
                                _count++;
                                break;
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// The internal method used by ContainsKey(string) method.
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private int ContainsKeyInternal(string key)
        {
            uint hashA, hashB;
            uint hash;
            HashProvider.GetHashCodes(key, out hashA, out hashB);
            for (int i = 0; i < NumHashes; i++)
            {
                hash = hashA + _primes[i] * hashB;
                if (!_spaceMap[(int)(hash & (this.Capacity - 1))])
                    break;
                else if (_entries[hash & (Capacity - 1)].HashA == hashA && _entries[hash & (Capacity - 1)].HashB == hashB)
                    return (int)(hash & (Capacity - 1));
            }
            return -1;
        }

        /// <summary>
        /// The internal method called to resize the _entries array.
        /// Complexity O(n)
        /// </summary>
        private void Resize()
        {
            StringValueBagEntry<T>[] newEntries = new StringValueBagEntry<T>[(Capacity << 1)];
            BitArray newSpaceMap = new BitArray(Capacity << 1);
            BitArray newValueSpaceMap = new BitArray(GetNextPrime(Capacity * _numHashesValue)); 
            uint hash;

            for (int i = 0; i < _entries.Length; i++)
            {
                if (_spaceMap[i])
                {
                    for (int j = 0; j < NumHashes; j++)
                    {
                        hash = _entries[i].HashA + _primes[j] * _entries[i].HashB;
                        if (! newSpaceMap[(int)(hash & (newEntries.Length - 1))])
                        {
                            newEntries[hash & (newEntries.Length - 1)] = _entries[i];
                            newSpaceMap[(int)(hash & (newEntries.Length - 1))] = true;
                            for (int k = 0; k < _numHashesValue; k++)
                            {
                                if (ValueHashProvider == null)
                                    newValueSpaceMap.Set((int)(_entries[i].Value.GetHashCode() * _primes[k]) % newSpaceMap.Count, true);
                                else
                                    newValueSpaceMap.Set((int)(_entries[i].Value.GetHashCode() * _primes[k]) % newSpaceMap.Count, true);
                            }
                            break;
                        }
                    }
                }
            }

            _entries = newEntries;
            _spaceMap = newSpaceMap;
            _valueSpaceMap = newValueSpaceMap;
        }

        /// <summary>
        /// Returns the next Prime greater than the given number.
        /// </summary>
        /// <param name="current"></param>
        /// <returns></returns>
        private int GetNextPrime(int current)
        {
            bool flag;
            current++;
            while (true)
            {
                flag = true;
                for (int i = 0; i < _primes.Length; i++)
                {
                    if (current % _primes[i] == 0)
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                {
                    for (int i = 2031; i < Math.Sqrt(current) + 1; i += 2)
                    {
                        if (current % i == 0)
                        {
                            flag = false;
                            break;
                        }
                    }
                }
                if (flag)
                    break;
                else
                    current++;
            }
            return current;
        }

        /// <summary>
        /// Returns the next capacity greater than the given number. Capacities are powers of 2.
        /// </summary>
        /// <param name="currentCapacity"></param>
        /// <returns></returns>
        private int GetNextCapacity(int currentCapacity)
        {
            for (int i = 10; i < 31; i++)
            {
                if ((2 << i) >= currentCapacity)
                    return 2 << i;
            }
            throw new Exception("Capacity could not be found for currentCapacity: " + Capacity);
        }

        /// <summary>
        /// Add given Dictionary<string,T> to present collection
        /// </summary>
        /// <param name="collection"></param>
        private void AddCollection(IDictionary<string, T> collection)
        {
            foreach (string key in collection.Keys)
            {
                Add(key, collection[key]);
            }
            _count += collection.Count;
        }

        private void UpdateValueSpaceMapInsert(T val)
        {
            for (int i = 0; i < _numHashesValue; i++)
            {
                if (ValueHashProvider == null)
                    _valueSpaceMap.Set((int)(val.GetHashCode() * _primes[i]) % _valueSpaceMap.Count, true);
                else
                    _valueSpaceMap.Set((int)(ValueHashProvider.GetHashCode(val) * _primes[i]) % _valueSpaceMap.Count, true);
            }
        }

        private void UpdateValueSpaceMapRemove(T val)
        {
            for (int i = 0; i < _numHashesValue; i++)
            {
                if (ValueHashProvider == null)
                    _valueSpaceMap.Set((int)(val.GetHashCode() * _primes[i]) % _valueSpaceMap.Count, false);
                else
                    _valueSpaceMap.Set((int)(ValueHashProvider.GetHashCode(val) * _primes[i]) % _valueSpaceMap.Count, false);
            }
        }
               
        /// <summary>
        /// Some primes to help speed up prime calculation
        /// </summary>
        private readonly uint[] _primes = new uint[]   {
                                                2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029
                                            };
        #endregion
    }

    public struct StringValueBagEntry<T> where T : IEquatable<T>
    {
        #region Properties

        private uint _hashA;
        public uint HashA
        {
            get { return _hashA; }
            set { _hashA = value; }
        }

        private uint _hashB;
        public uint HashB
        {
            get { return _hashB; }
            set { _hashB = value; }
        }

        private T _value;
        public T Value
        {
            get { return _value; }
            set { _value = value; }
        }
        #endregion

        public StringValueBagEntry(uint hashA, uint hashB, T val)
        {
            _hashA = hashA;
            _hashB = hashB;
            _value = val;
        }
    }
}
